import heapq


class Solution(object):
    def connectSticks(self, sticks):
        """
        :type sticks: List[int]
        :rtype: int
        """
        heapq.heapify(sticks)
        index = 0
        node = [0, 0]
        total = 0
        while sticks:
            value = heapq.heappop(sticks)
            node[index] = value
            index += 1
            if index == 2:
                sum_value = sum(node)
                total += sum_value
                index = 0
                node = [0, 0]
                heapq.heappush(sticks, sum_value)
        return total


data = Solution()
sticks = [2, 4, 3]
print(data.connectSticks(sticks))
sticks = [1, 8, 3, 5]
print(data.connectSticks(sticks))
sticks = [5]
print(data.connectSticks(sticks))
sticks = [3354, 4316, 3259, 4904, 4598, 474, 3166, 6322, 8080, 9009]
print(data.connectSticks(sticks))
